//给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其
//中 n 也是一个整数。 
//
// 
//
// 示例 1： 
//
// 输入：[23,2,4,6,7], k = 6
//输出：True
//解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
// 
//
// 示例 2： 
//
// 输入：[23,2,6,4,7], k = 6
//输出：True
//解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
// 
//
// 
//
// 说明： 
//
// 
// 数组的长度不会超过 10,000 。 
// 你可以认为所有数字总和在 32 位有符号整数范围内。 
// 
// Related Topics 数学 动态规划 
// 👍 141 👎 0

package leetcode.editor.cn;

import com.sun.org.apache.regexp.internal.RE;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//Java：连续的子数组和
public class P523ContinuousSubarraySum {
    public static void main(String[] args) {
        Solution solution = new P523ContinuousSubarraySum().new Solution();
        int[] arr = {1, 0};

        boolean res = solution.checkSubarraySum(arr, 2);
        System.out.println(res);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*
         * 暴力破解
         * */
        public boolean checkSubarraySum1(int[] nums, int k) {
            if (nums == null || nums.length <= 0) {
                return false;
            }
            if (k == 0) {
                //return true;
                for (int i = 0; i < nums.length - 1; i++) {
                    if (nums[i] == 0 && nums[i + 1] == 0) {
                        return true;
                    }
                }
                return false;
            }
            int len = nums.length;
            for (int i = 0; i < len; i++) {
                int sum = nums[i];
                for (int j = i + 1; j < len; j++) {
                    sum += nums[j];
                    if (sum % k == 0) {
                        return true;
                    }
                }
            }

            return false;
        }

        /*
         * 分析一下暴力解法所存在的问题
         * （）两层 for循环  O(n^2)的时间复杂度
         *
         *  使用前缀和
         *  假设第i个位置sum的值为rem.
         *  若以i为左端点的任何子数组的和是k的倍数，即区间 [i,j]的和为k的倍数
         *  此时第j个位置的和应该为 rem+n*k, (rem+n*k)%k=rem
         *
         *  因此当两个位置i和j的前缀和对k取余相当的时候，该区间的和为k的倍数
         *
         * */
        public boolean checkSubarraySum(int[] nums, int k) {
            if (nums == null || nums.length <= 0) {
                return false;
            }

            /*
             * 使用HashMap来保存前缀和对k取余的结果
             * 使用ref[] 保存前缀和
             * */
            int len = nums.length;
            int[] ref = new int[len];
            Map<Integer, Integer> map = new HashMap<>();

            ref[0] = nums[0];
            map.put(0, -1);
            //  map.put(ref[0]%k,0);

            int sum = 0;


            for (int i = 0; i < nums.length; i++) {
                //   ref[i]=ref[i-1]+nums[i];
                sum += nums[i];
                if (k != 0) {
                    /*
                    1 0  k=2
                    * */
                    sum %= k;
                }
                if (map.containsKey(sum)) {
                    if (i - map.get(sum) > 1) {
                        return true;
                    }
                } else {
                    map.put(sum, i);
                }


            }
            return false;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}
